/**
 * Created with IntelliJ IDEA.
 * Description:
 * 查找树中p、q节点的最近公共祖先
 * User: xwl
 * Date: 2023-05-22
 * Time: 11:06
 */

class TreeNode1 {
    int val;
    TreeNode2 left;
    TreeNode2 right;
    TreeNode1(int x) { val = x; }
}

public class Test1 {

    /**
     * 查找p、q节点的最近公共祖先
     * @param root:树的根节点
     * @param p:待查找节点1
     * @param q:待查找节点1
     * @return null:没有公共祖先
     */
    public TreeNode2 lowestCommonAncestor(TreeNode2 root, TreeNode2 p, TreeNode2 q) {
        // 谈论root为空的情况
        if (root == null) {
            return null;
        }
        // 谈论树只有一个节点的情况
        if (root == p || root == q) {
            return root;
        }
        // 定义俩个节点接收递归孩子的返回值
        TreeNode2 left = lowestCommonAncestor(root.left,p,q);
        TreeNode2 right = lowestCommonAncestor(root.right,p,q);
        // 实现
        if (left != null && right != null) {
            return root;
        }else if (left != null) {
            return left;
        }else if (right != null) {
            return right;
        }
        // p、q都为空的情况
        return null;
    }
}
